package com.darrenchan.leetcode;

import java.util.Arrays;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-11-26 21:11
 */
public class Q115 {
    public int numDistinct(String s, String t) {
        if(s.length() < t.length()) return 0;
        if(t.length() == 0) return 1;
        //动态规划
        int slen = s.length(), tlen = t.length();
        int[][] dp = new int[slen][tlen];

        dp[0][0] = s.charAt(0) == t.charAt(0) ? 1 : 0;

        for (int i = 1; i < slen; i++) {
            if(s.charAt(i) == t.charAt(0)){
                dp[i][0] = dp[i - 1][0] + 1;
            }else{
                dp[i][0] = dp[i - 1][0];
            }
        }

        for (int j = 1; j < tlen; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i < slen; i++) {
            for (int j = 1; j < tlen; j++) {
                if(s.charAt(i) == t.charAt(j)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        for (int i = 0; i < slen; i++) {
            for (int j = 0; j < tlen; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[slen - 1][tlen - 1];
    }

    public int numDistinct2(String s, String t) {
        int m = s.length();
        int n = t.length();
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if(j == 0){
                    dp[i][j] = 1;
                    continue;
                }

                if(i == 0){
                    dp[i][j] = 0;
                    continue;
                }

                dp[i][j] = dp[i - 1][j];
                if(ss[i - 1] == tt[j - 1]){
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(new Q115().numDistinct("babgbag", "bag"));
    }
}
